/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/the-maze
   @Language: C++
   @Datetime: 19-06-25 15:30
   */

class Solution {
public:
	/**
	 * @param maze: the maze
	 * @param start: the start
	 * @param destination: the destination
	 * @return: whether the ball could stop at the destination
	 */
	bool hasPath(vector<vector<int> > &maze, vector<int> &start, vector<int> &destination) {
		// write your code here
		int row=maze.size(), col=maze[0].size();
		queue<long> q;
		unordered_set<long> visit;
		for(q.push(((start[0]+0L)<<32)|start[1]); q.size(); q.pop()){
			const int i=q.front()>>32, j=q.front()&0xFFFFFFFF;
			if(i<0 || i>=row || j<0 || j>=col) continue;
			if(maze[i][j]==1) continue;
			if(visit.count(q.front())) continue;
			visit.insert(q.front());
			if(i==destination[0] && j==destination[1]) return true;
			int r, c;
			for(r=i, c=j; r+1<row && maze[r+1][c]==0; ++r);
			q.push(((r+0L)<<32)|c);
			for(r=i, c=j; r-1>=0 && maze[r-1][c]==0; --r);
			q.push(((r+0L)<<32)|c);
			for(r=i, c=j; c+1<col && maze[r][c+1]==0; ++c);
			q.push(((r+0L)<<32)|c);
			for(r=i, c=j; c-1>=0 && maze[r][c-1]==0; --c);
			q.push(((r+0L)<<32)|c);
		}
		return false;
	}
};
